package com.lans.SortAlgorithm;

import java.util.Arrays;

/**
 * @author: lans
 * @date: 2025/2/12
 * @name: 刘宇
 */
public class MergeSort1 {
    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 1, 56, 87, 212, 3};
        int[] temp = new int[arr.length];
        mSort(arr, 0, arr.length - 1, temp);
        System.out.println(Arrays.toString(arr));
    }

    public static void mSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            //先分解左区间 直至有序即分解成单个元素即left=right
            mSort(arr, left, mid, temp);
            //在分解右区间
            mSort(arr, mid + 1, right, temp);
            //进行归并操作
            merge(arr, left, right, mid, temp);
        }
    }

    public static void merge(int[] arr, int left, int right, int mid, int[] temp) {
        int i = left;//左边序列开始的位置
        int j = mid + 1;//右边序列开始的位置
        int t = 0;//临时数组的下标
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        //将左边有序序列剩余的元素平移到临时数组中来
        while (i <= mid) {
            temp[t] = arr[i];
            t++;
            i++;
        }
        //将右边有序序列剩余的元素平移到临时数组中来
        while (j <= right) {
            temp[t] = arr[j];
            t++;
            j++;
        }
        //将临时数组拷贝回原数组
        t = 0;
        while (left <= right) {
            arr[left] = temp[t];
            left++;
            t++;
        }

    }
}